Text Justification

Description#

We are given an array of strings and a maximum width. We have to format the input words in the same order and into several rows with n columns. The words must be formatted such that each line has exactly n characters, one in each column, except possibly the last line. We must squeeze as many words as possible into each line, with at least one space between each pair of consecutive words. The first word on each line must start at the left-most column.

The last word on each line must end at the right-most column, unless only one word can fit on a line. More than one space between words may need to be inserted to ensure that the first word in a line starts at the first column and the last word ends at the last column. In such cases, we will insert an approximately equal number of spaces between each pair of words. If the spaces can’t be evenly spread between the words on a line, then the first two words will get more spaces than all the other word pairs, which will be spaced equally.

The last line must start on the left-most column, but may end before the last column. Only one space between each pair of words must be used on the last line. We will put as many words as we can in each line. We will add extra spaces, when necessary, so that each line has exactly the given width of characters. We will distribute extra spaces between words as evenly as possible. Otherwise, the empty slots on the left will have more spaces than the slots on the right.

Note: A word consists of non-space characters only. Each word’s length must be greater than 0 and should not exceed the given width. The input array will contain at least one word.

Constraints#

• 1 <= words.length <= 300
• 1 <= words[i].length <= 20
• 1 <= width <= 100
• words[i].length <= width
• words[i] consists of only English letters and symbols.

Let’s see the example in the following illustration:

Coding exercise#

Solution#

We have an array of words and a maximum line width. We will put words in a line by traversing the array, and each line length will be equal to the given width.

Let’s see the algorithm that is used to implement the problem described above:

• First, we will find out where to cut the array of words by setting the given width as a threshold.

• Generally, we will use a single space between words to make a line.

• If extra space exists at the end of the line, we will evenly distribute the spaces between the words.

• We will compute the extra spaces by subtracting the given width from the current line length and then dividing it by (j - 1 - i) + 1, where j will represent the current line length and i will represent the current string index of the given array.

• Next, we will add the extra spaces between the words of the current line.

• For the last line, we will add a single space between the words and add the extra spaces after the last word of the line.

Let’s understand this algorithm with the illustration given below:

Let’s look at the code for this solution:

Complexity measures#

Time complexity#

We will traverse the given array of words exactly once, so the time complexity will be $O(n)$, where n will be the size of the array.

Space complexity#

The space complexity will be $O(1)$ for this problem.